// 旋转treap
// https://www.luogu.com.cn/problem/P3369
// https://soj.turingedu.cn/problem/60300/
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
int rad(); // read int
const int max_size = 5 + 100;
const int maxn = 5 + 1e6;

int tsiz, root;
struct Node {
    int val, w, siz;
} pool[maxn];
int ch[maxn][2];
class Treap {
  private:
    inline int new_node(int x) {
        pool[++tsiz] = {x, rand(), 1}, ch[tsiz][0] = ch[tsiz][1] = 0;
        return tsiz;
    }
    inline void push_up(int now) {
        pool[now].siz = pool[ch[now][0]].siz + pool[ch[now][1]].siz + 1;
    }
    void rotate(int &now, int d) {
        int sub = ch[now][d ^ 1];
        ch[now][d ^ 1] = ch[sub][d], push_up(now);
        ch[sub][d] = now, push_up(sub), now = sub;
    }

  public:
    int insert(int &u, int x) {
        if (u == 0) return u = new_node(x);
        int d = (x > pool[u].val), ret = insert(ch[u][d], x);
        if (pool[ch[u][d]].w > pool[u].w) rotate(u, d ^ 1);
        push_up(u);
        return ret;
    }

    int erase(int &u, int x) {
        if (u == 0) return 0;
        if (pool[u].val != x) {
            int ret = erase(ch[u][x > pool[u].val], x);
            if (ret) push_up(u);
            return ret;
        }
        int ret = u;
        if (ch[u][0] == 0 || ch[u][1] == 0) {
            u = ch[u][0] | ch[u][1];
        } else {
            int d = (pool[ch[u][1]].w > pool[ch[u][0]].w);
            rotate(u, d ^ 1), erase(ch[u][d ^ 1], x), push_up(u);
        }
        return ret;
    }
} treap;

int get_rank(int u, int x) { // return inf for no find
    int lsiz = 0;
    while (u) {
        if (x > pool[u].val) lsiz += pool[ch[u][0]].siz + 1;
        u = ch[u][x > pool[u].val];
    }
    return lsiz;
}

int get_val(int u, int rk) {
    while (u) {
        int now_rk = pool[ch[u][0]].siz + 1;
        if (rk == now_rk) return pool[u].val; // find
        u = ch[u][rk > now_rk];
        if (rk > now_rk) rk -= now_rk;
    }
    return 0;
}

int get_pre(int u, int x) {
    int ret = -inf;
    while (u) {
        if (x > pool[u].val) ret = max(ret, pool[u].val);
        u = ch[u][x > pool[u].val];
    }
    return ret;
}

int get_nex(int u, int x) {
    int back = inf;
    while (u) {
        if (x < pool[u].val) back = min(back, pool[u].val);
        u = ch[u][x >= pool[u].val];
    }
    return back;
}

void show(int p = root, int dep = 1) {
    if (p == 0) return;
    show(ch[p][0], dep + 1);
    printf("|| val: %d, deep: %d, siz: %d, p: %d\n", pool[p].val, dep, pool[p].siz, p);
    show(ch[p][1], dep + 1);
}
